
/* https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/submissions/571293480/ */
/*1011. 在 D 天内送达包裹的能力 */
/* /* 难度：简单 时间10/9 */
/* 二分搜索 */ * /

    代码： class Solution
{
public:
    int shipWithinDays(vector<int> &weights, int days)
    {
        // 思路：先遍历找到所有重量中的最小值赋值给它的左边界，然后把所有重量的和赋值给右边界(最多全部装满一天搬走),用二分法去猜出最佳答案
        int l = INT_MAX;
        int r = 0;
        for (auto x : weights)
        {
            l = min(l, x);
            r += x;
        }
        while (l < r)
        {
            int min = l + (r - l) / 2;
            if (checkok(weights, min, days))
            {
                r = min;
            }
            else
            {
                l = min + 1;
            }
        }
        return l;
    }

    bool checkok(vector<int> &weight, int min, int days)
    {
        int count = 0;
        for (int i = 0; i < weight.size(); i++)
        {
            int j = i;
            int sum = 0;
            while (j < weight.size() && sum + weight[j] <= min)
            {
                sum += weight[j];
                j++;
            }
            count += 1;
            if (count > days)
                return false;
            i = j - 1;
        }
        return true;
    }
};